package LC;

import java.util.ArrayList;
import java.util.List;

public class LC57 {

    public static void main(String[] args) {
        int [][]intervals = {{1,3},{6,9}};
        int []newInterval ={2,5};
        int [][]res=insert(intervals,newInterval);
        System.out.println(res.toString());
    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res=new ArrayList<>();
        int left=newInterval[0];
        int right=newInterval[1];
        boolean flag=false;
        for(int[] target:intervals){
            if(target[0]>right){
                if(!flag){
                    res.add(new int[]{left,right});
                    flag=true;
                }
                res.add(target);
            }else{
                if(target[1]<left){
                    res.add(target);
                }else{
                    left=Math.min(left,target[0]);
                    right=Math.max(right,target[1]);
                }
            }
        }
        if(!flag){
            res.add(new int[]{left,right});
        }
        int [][]arr=new int[res.size()][2];
        for(int i=0;i<res.size();i++){
            arr[i][0]=res.get(i)[0];
            arr[i][1]=res.get(i)[1];
        }
        return arr;
    }
}
